#include "BFSOnCompactGraph.h"

#include "CompactGraph.h"

#include <vector>


namespace native_orbitor
{

BFSOnCompactGraph::BFSOnCompactGraph()
{
}

bool BFSOnCompactGraph::isApplicable2graph( GRAPH_SUPPORT_NS::Graph * abstractGraphPtr )
{
	CompactGraph * compactGraphPtr = dynamic_cast< CompactGraph * >( abstractGraphPtr );
	return compactGraphPtr != NULL;
}

void BFSOnCompactGraph::runOnGraph( GRAPH_SUPPORT_NS::Graph * abstractGraphPtr )
{
	assert( isApplicable2graph( abstractGraphPtr ) );
	CompactGraph * compactGraphPtr = dynamic_cast< CompactGraph * >( abstractGraphPtr );
	CompactGraph & gr = * compactGraphPtr;

	int n = gr.getVertexCount();
	std::vector< int > queueBuf( n );
	int * qhead = & queueBuf[0];
	int * qtail = qhead;
	int * qlim = qhead + n;
	char NEW = 0;
	char QUEUED = 1;
	char COMPLETED = 2;
	std::vector< char > statesBuf( n, NEW );
	char * states = & statesBuf[0];

	int startVert = 0;
	* qtail = startVert;
	qtail++;
	states[startVert] = QUEUED;
	while ( qhead < qtail )
	{
		int v = * qhead;
		qhead++;
		assert( states[v] == QUEUED );
		for ( int j = gr.st[v]; j > -1; j = gr.nx[j] )
		{
			int d = gr.dest[j];
			if ( states[d] == NEW )
			{
				assert( qtail < qlim );
				* qtail = d;
				qtail++;
				states[d] = QUEUED;
			}
		}
		states[v] = COMPLETED;
	}
}

}
